package leetcode_2601_2700;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class LeeCode_2607_02 {
    public static void main(String[] args) {
        System.out.println(makeSubKSumEqual(new int[]{1, 4, 1, 3}, 2));
    }
    private static long makeSubKSumEqual(int[] arr, int k) {
        int n = arr.length;
        k = gcd(k, n);
        long ans = 0;
        for (int i = 0; i < k; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = i; j < n; j += k) {
                list.add(arr[j % n]);
            }
            list.sort(Comparator.comparingInt(o -> o));
            for (Integer num : list) {
                ans += Math.abs(num - list.get(list.size() / 2));
            }
        }
        return ans;
    }
    private static int gcd(int x, int y){
        int min = Math.min(x, y), max = Math.max(x, y);
        while (min != 0){
            int tmp = min;
            min = max % min;
            max = tmp;
        }
        return max;
    }
}
